def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(1))

print(fact(5))

# 栈溢出
# print(fact(1000))

# 解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的
def fact(n):
    return fact_iter(n, 1)

# 尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。
# 这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, product * num)


print(fact(5))

def mov(n, a, b, c):
    if n == 1:
        print(a, '-->', b)
        return
    mov(n-1, a, c, b)
    print(a, '-->', b)
    mov(n-1, c, b, a)

mov(4, 'A', 'B', 'C')


"""
此时B是A的跳板
A->C 小的暂存到C
A->B 大的放到B
C->B 小的放到大的上面
A->C 更大的放到C
--- 此时上面两个在B，最大的在C, 一阶段移动成功 --

--- 把B看作A，把A看作B, 此时A是B到C的跳板, C还是C，再移动第二大的 --
B->A 小的暂存A
B->C 大的放到C
-- 此时C成功移动两个，A剩余1个，二阶段移动成功

--- 最后还剩一个在A，直接从A放到C ---
A->C 

规律：
目标1：移动最底下的一个到C，剩余的暂存B
A->C
A->B
C->B
A->C
状态1：第三个到了C，上面的两个到了B

B->A
B->C
A->C
状态2：三个到了C，其余留在A




"""